package _01_sort.leetcodeexerc;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/24 - 6:36
 * 使用时间复杂度为O(n)的排序算法，基数排序
 */
public class Test3 {

    @Test
    public void test() {
        int[] arr = {1020, 0, 3, 43, 62, 217, 11, 54};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    void radixSort(int[] arr) {
        List<List<Integer>> buckets = new ArrayList<>(10);
        // 初始化桶
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }

        for (int i = 0; i < getMaxDigits(arr); i++) {
            for (int k : arr) {
                // 求得位数
                int digit = getDigit(k, i);
                // 添加到对应的下标位置
                buckets.get(digit).add(k);
            }

            // 从桶中取出元素
            int index = 0;
            for (List<Integer> bucket : buckets) {
                for (Integer value : bucket) {
                    arr[index++] = value;
                }
                bucket.clear();
            }
        }
    }

    /**
     * 求 num 的位数值
     *
     * @param num
     * @param dig 位数
     * @return
     */
    int getDigit(int num, int dig) {
        /*
            求各位数 num / 1 % 10
            求十位数 num / 10 % 10
            求百位数 num / 100 % 10
            求千位数 num / 1000 % 10
            求万位数 num / 10000 % 10
            ...
         */
        return (num / (int) Math.pow(10, dig)) % 10;
    }

    /**
     * 获取数组中最大元素的长度
     *
     * @param arr
     * @return
     */
    int getMaxDigits(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        if (max == 0) {
            return 1;
        }
        return (int) (Math.log10(max) + 1);
    }

}
